#include <string>
#include <unordered_map>
#include <vector>

using namespace std;


class Solution {
public:
    string intToRoman(int num) {
        vector<int> numbers{1,4,5,9,10,40,50,90,100,400,500,900,1000};
        unordered_map<int, string> table;
        table[1] = "I";
        table[4] = "IV";
        table[5] = "V";
        table[9] = "IX";
        table[10] = "X";
        table[40] = "XL";
        table[50] = "L";
        table[90] = "XC";
        table[100] = "C";
        table[400] = "CD";
        table[500] = "D";
        table[900] = "CM";
        table[1000] = "M";

        string res;
        int n = 1, div=10, num_ = num;
        while (num_ /= 10) {
            n++;
            div *= 10;
        }

        for (int i=n-1; i>=0; i--) {
            div /= 10;
            int head = (num / div) * div;  // 头部数字带零
            num -= head;                   // 剩余数字
            // The leading number is one of 1, 4, 5, 9
            if (table.count(head)) {
                res += table[head];
                continue;
            }
            // Now the leading number is one of 2, 3, 6, 7, 8
            while (head) {
                if (head / div > 5) {  // 减去5开头
                    res += table[5*div];
                    head -= 5*div;
                } else {
                    res += table[div];
                    head -= div;
                }
            }
        }

        return res;
    }
};
